// 有效括号  进站出站
function valid(s: string) {
  const stack: string[] = [];
  if (s.length % 2 != 0) return false;
  for (let ch of s) {
    switch (ch) {
      case "(":
        stack.push(")");
        break;
      case "[":
        stack.push("]");
        break;
      case "{":
        stack.push("}");
        break;
      default:
        if (stack.pop() === ch) break;
        return false;
    }
  }
  return stack.length === 0;
}
// console.log(valid("([{}])"));

// 2数之和
function sum2(nums: number[], target: number) {
  const map = new Map();
  for (let i in nums) {
    const need = target - nums[i];
    if (map.has(need)) return [i, map.get(need)];
    map.set(nums[i], i);
  }
}
// console.log(sum2([2, 7, 11, 15], 9));

type ListNode = {
  val: number;
  next: ListNode;
} | null;
const list: ListNode = {
  val: 2,
  next: {
    val: 3,
    next: { val: 1, next: null },
  },
};
// 链表排序
function sortList(head: ListNode) {
  let tail = head;
  const res: number[] = [];
  while (tail) {
    res.push(tail.val);
    tail = tail.next;
  }
  res.sort((a, b) => a - b);

  tail = head;
  let i = 0;
  while (tail) {
    tail.val = res[i];
    tail = tail.next;
    i++;
  }
  return head;
}
// console.log(sortList(list));

// 合并有序链表
function mergeList(list1: ListNode, list2: ListNode) {
  const res: ListNode = { val: -1, next: null };

  let cur = res;
  while (list1 && list2) {
    if (list1.val > list2.val) {
      cur.next = list2;
      list2 = list2.next;
    } else {
      cur.next = list1;
      list1 = list1.next;
    }
    cur = cur.next;
  }
  cur.next = list1 || list2;
  return res.next;
}
// 递归写法
function merge2List(list1: ListNode, list2: ListNode): ListNode {
  if (!list1) return list2;
  if (!list2) return list1;

  if (list1.val <= list2.val) {
    list1.next = merge2List(list1.next, list2);
    return list1;
  } else {
    list2.next = merge2List(list2.next, list1);
    return list2;
  }
}

// 买卖股票的时机
function maxProfit(prices: number[]) {
  let base = prices[0];
  let max = 0;
  for (const num of prices) {
    base = Math.min(base, num);
    max = Math.max(max, num - base);
  }
  return max;
}

// 无重复字符的最长子串
function maxString(str: string) {
  let max = 0;
  let child = "";
  for (const ch of str) {
    const index = child.indexOf(ch);
    if (index !== -1) {
      max = Math.max(child.length, max);
      child = child.slice(index + 1) + ch;
    } else {
      child += ch;
    }
  }
  max = Math.max(child.length, max);
  return max;
}
// console.log(maxString("dvdf"));

// 滑动窗口写法
function slideWindow(str: string) {
  let set = new Set<string>();
  let left = 0,
    max = 0;
  for (let right = 0; right < str.length; right++) {
    // 移动左边界
    while (set.has(str[right])) {
      set.delete(str[left]);
      left++;
    }
    set.add(str[right]);
    max = Math.max(max, set.size);
  }
  return max;
}

// 最大子数组和
function maxArrChild(nums: number[]) {
  let max = nums[0];
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    max = Math.max(sum, max);
    if (sum < 0) sum = 0;
  }
  return max;
}
// console.log(maxArrChild([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

// 反转链表
function simple(head: ListNode) {
  let tail = head;
  const res: number[] = [];
  while (tail) {
    res.push(tail.val);
    tail = tail.next;
  }
  tail = head;
  while (tail) {
    tail.val = res.pop()!;
    tail = tail.next;
  }
  return head;
}
function reverse(head: ListNode) {
  let res: ListNode = null;
  while (head) {
    let temp = head.next;
    head.next = res;
    res = head;
    head = temp;
  }
  return res;
}

// 最小栈
class MiniStack {
  private arr: number[] = [];
  private minArr: number[] = [Infinity];

  push(val: number) {
    this.arr.push(val);
    this.minArr.push(Math.min(val, this.minArr[this.minArr.length - 1]));
  }
  pop() {
    this.arr.pop();
    this.minArr.pop();
  }
  top() {
    return this.arr[this.arr.length - 1];
  }
  getMin() {
    return this.minArr[this.minArr.length - 1];
  }
}
// const stack = new MiniStack();
// stack.push(1);
// stack.push(-4);
// stack.push(-1);
// console.log(stack.top(), stack.getMin());

// 买卖股票的最佳时机2
function maxProfit2(prices: number[]) {
  let base = prices[0];
  let sum = 0;
  for (let num of prices) {
    if (base < num) sum += num - base;
    base = num;
  }
  return sum;
}

// 岛屿数量
function isLand(org: string[][]) {
  const arr = org.map((row) => [...row]);
  let num = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      if (arr[i][j] !== "1") continue;
      num++;
      walk(i, j);
    }
  }
  return num;

  // 访问格子的四个方向
  function walk(i: number, j: number) {
    // 过界或非陆地或访问过
    if (arr?.[i]?.[j] !== "1") return;
    arr[i][j] = "2";
    walk(i + 1, j);
    walk(i - 1, j);
    walk(i, j + 1);
    walk(i, j - 1);
  }
}
const arr = [
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"],
];
// console.log(isLand(arr));

function isLand2(org: string[][]) {
  const arr = org.map((row) => [...row]);
  let num = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      if (arr[i][j] !== "1") continue;
      num++;
      walk(i, j);
    }
  }
  function walk(i, j) {
    // 过界或非陆地或访问过
    if (arr?.[i]?.[j] !== "1") return;
    arr[i][j] = "2";
    walk(i + 1, j);
    walk(i - 1, j);
    walk(i, j + 1);
    walk(i, j - 1);
  }
  return num;
}
// console.log(isLand2(arr));

// 2数之和
function sumIndex2(arr: number[], target: number): [number, number] {
  const map = new Map<number, number>();
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    const need = target - num;
    if (map.has(need)) return [map.get(need)!, i];
    map.set(num, i);
  }
  return [-1, -1];
}
const arr1 = [2, 7, 11, 15],
  target1 = 24;
const arr2 = [3, 2, 4],
  target2 = 6;

// console.log(getSumIndex(arr1, 12));
// console.log(getSumIndex(arr2, target2));

// 3数之和
function sum3(arr: number[], target: number) {
  for (let k = 0; k < arr.length; k++) {
    const need = target - arr[k];
    const res = sumIndex2(arr, need);
    if (res.includes(-1)) continue;
    return [k, ...res];
  }
  return [-1, -1, -1];
}
console.log(sum3(arr1, target1));
